1. Field of the Invention
This invention relates generally to data processing systems and, more particularly, to execution of the multiplication procedure by a data processing system.
2. Description of the Related Art
Data processing systems typically employ an array of carry/save adders to execute the multiplication procedure. A block diagram of apparatus used in performing this multiplication procedure is shown in FIG. 1. Register 101 contains the multiplicand operand, while register 102 contains the multiplier operand. For this exemplary apparatus, the operands are assumed to be 8 bits in length. The multiplication apparatus includes a first carry/save adder stage 111, a second carry/save adder stage 112, a third carry/save adder stage 113 and a fourth carry/save adder stage 114. In the exemplary apparatus illustrated in FIG. 1, a shift of two bit positions is assumed between each carry/save adder stage (i.e., a two bit retirement algorithm is used). Each carry/save adder stage includes a multiplicity of carry/save adder cells, in the present example 8 carry/save adder cells are used in each stage.
Referring now to FIG. 2, (for the modified Booth's 2 bit retirement algorithm) each carry/save adder cell 20 has a CARRY(n+1) signal from the prior carry/save adder stage, a SUM(n+2) signal from the prior carry/save adder stage and a MULTIPLICAND(n) signal applied thereto and, in response to control signals, provides a SUM(n) signal and a CARRY(n) signal. (Each carry/save adder cell is associated with a multiplicand bit position n.)
Referring again to FIG. 1, each multiplicand register 101 cell is applied to a corresponding carry/save adder cell in each of the carry/save adder stages. In FIG. 1, this coupling is illustrated for the 7.sup.th bit position of multiplicand register 101 which is coupled to the 7.sup.th bit position carry/save adder cell of the first carry/save adder stage 111, the 7.sup.th bit position carry/save adder cell of the second carry/save adder stage 112, the 7.sup.th bit position carry/save adder cell of the third carry/save adder stage 113 and the 7.sup.th bit position carry/save adder cell of the fourth carry/save adder stage 114. In the illustrative example of FIG. 1, the two bit position shift between the carry/save adder stages in indicated in FIG. 1 by the application of the SUM (S) signal from carry/save adder cell bit position 5 to the carry/save adder cell bit position 3 of the next succeeding carry/save adder stage and by the application of the CARRY (C) signal from carry/save adder cell bit position 5 to the carry/save adder cell at bit position 4 of the next succeeding carry/save adder stage (i.e., from carry/save adder stage 111 to carry/save adder stage 112, etc.).
The two position shifting of signals between the carry/save adder stages is the result of using a procedure generally referred to as the modified Booth 2 bit retirement algorithm. In this procedure, a plurality (2 bits in the present example) of remaining least significant multiplier operand bits multiply the multiplicand operand in a single operation (i.e., are retired in a single operation). This operation is performed by encoding (or recoding the two multiplier bits into appropriate control signals in encoding apparatus 141, 142, 143 and 144, each encoding apparatus being associated with a carry/save adder stage (111, 112, 113 and 114 respectively). (As will be known to those familiar with the modified Booth algorithm, the remaining three least significant bits are used to determine the control signals even though only the two least significant bits are retired.) Referring to FIG. 3, the relationship between the three multiplier bits and the operation of the carry/save adder cell resulting from the control signals is illustrated. Of particular importance to the present invention is the requirement of the subtraction operation for certain multiplier operand signal groups. In order to implement the subtraction operation with the carry/save adder cells, the 2's complement subtraction algorithm is used. When the encoding apparatus 141 to 144 determines that a subtraction operation is to be performed in the associated carry/save adder logic (111 through 114 respectively), a 1's complement signal group is formed from the multiplicand operand and the logic signal, to complete the 2's complement of the multiplicand operand, is applied to the least significant bit position associated with the multiplicand operand.
Referring once again to FIG. 1, the shifting operation causes a portion of the operand field to be removed therefrom. To insure the accuracy of the multiplication procedure, least significant cells 151, 152, 153 and 154 are used to process signals, otherwise removed from the operand field, but which can contribute to the result. In the preferred embodiment, the least significant cell is a two bit adder cell. The least significant cell receives the SUM signals from the 0.sup.th and 1.sup.st carry/save adder stage bit positions from the prior carry/save adder stage, the CARRY signal from the 0.sup.th bit position from the prior carry/save adder stage, the overflow signal from the preceding least significant cell and the logic signal needed to provide the 1's complement signal group, generated on the fly in the preferred embodiment, into a 2's complement signal for the prior carry/save adder stage. In the shifting of the signals from the carry/save adder stage, the least significant bit position associated with the multiplicand register is entered into the least significant cell and the application of the 2's complement logic signal thereto is equivalent to applying the 2's complement logic signal to the least significant position of the next preceding carry/save adder stage. The signals from the fourth carry/save adder stage 114 and the fifth least significant cell 154 are applied to the carry/sum combining network 130 wherein an 8 bit result operand is formed. (Least significant bit cell 150 is shown with dotted lines in FIG. 1 because all of the input signals thereto are zero.)
The multiplier circuit of FIG. 1 has several advantages. Only in carry/sum combining network 130 are the CARRY signals and the SUM signals combined into a single operand with the potentially slow carry propagation process. The use of the modified Booth algorithm reduces the number of operations performed on the operand and reduces the number of elements to implement the multiplication operation. However, the multiplication process has the limitation of potentially requiring the processing of five input signals by the least significant cell.
A need has therefore been felt for accelerating the potentially slowest portion of the multiplication procedure, which is the combination of signals in the least significant cell associated with each carry/save stage.